package datastructure.linkedlist;

/**
 * 单链表
 * @author lbw
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode node1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");

        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addOrder(node1);
        linkedList.addOrder(node3);
        linkedList.addOrder(node2);
        linkedList.show();
        System.out.println("-------反转------");
        linkedList.reverse();
        linkedList.show();
    }
}

/**
 * 定义单链表
 */
class SingleLinkedList{
    /**
     * 先初始化一个头结点，头结点不要动,不存放具体的数据
     */
    private HeroNode head = new HeroNode(0, "", "");

    private int size;

    /**
     * 添加一个节点,当不考虑编号的顺序时，找到当前链表的最后节点，将最后这个节点的next指向新的节点
     * @param node
     */
    public void add(HeroNode node){
        //因为head节点不能动，因此需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (temp.next != null){
            temp = temp.next;
        }
        temp.next = node;
        size++;
    }

    /**
     * 按编号插入
     */
    public void addOrder(HeroNode node){
        HeroNode temp = head;
        while (temp.next != null){
            if (temp.next.no > node.no){
                node.next = temp.next;
                temp.next = node;
                size++;
                return;
            }
            temp = temp.next;
        }
        temp.next = node;
        size++;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 找到需要被删除的节点的上一个节点，将上一个节点的next指向要被删除的节点的next
     * @param index
     */
    public void delete(int index){
        HeroNode temp = head;
        if (index >= size){
            System.out.println("链表下标越界");
            return;
        }
        for (int i = 0; i < index; i++){
            temp = temp.next;
        }
        temp.next = temp.next.next;
        size--;
    }

    /**
     * 显示链表
     */
    public void show(){
        if (isEmpty()){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        while (temp.next != null){
            temp = temp.next;
            System.out.println(temp.toString());
        }
    }

    /**
     * 查找单链表中的倒数第index个节点 (新浪面试题)
     * @param index
     * @return
     */
    public HeroNode getLastIndexNode(int index){
        if (index > size){
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0; i < (size - index); i++){
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 链表的反转
     */
    public void reverse(){
        if (size == 1 || size == 0){
            return;
        }
        //定义一个辅助的指针,帮助我们遍历原来的链表
        HeroNode cur = head.next;
        //指向当前节点cur的下一个节点
        HeroNode next = null;
        HeroNode reverse = new HeroNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur != null){
            next = cur.next;
            cur.next = reverse.next;
            reverse.next = cur;
            cur = next;
        }
        head.next = reverse.next;
    }
}
/**
 * 每个heroNode就是一个节点
 */
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
